package com.LeeCode;

import java.util.PriorityQueue;

/**
 * 可以到达的最远建筑
 */

public class Code1642 {
    public static void main(String[] args) {
        int[] heights = {1,5,1,2,3,4};
        int bricks = 4, ladders = 1;
        System.out.println(new Code1642().furthestBuilding(heights, bricks, ladders));

    }

    public int furthestBuilding(int[] heights, int bricks, int ladders) {
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
        int index = 0;
        while (index < heights.length - 1) {
            if (heights[index] >= heights[index + 1]) {
                index++;
                continue;
            }

            int need = heights[index + 1] - heights[index];

            // 有砖块用砖块
            if (need <= bricks) {
                bricks -= need;
                pq.offer(need);
            } else if (ladders > 0) { // 没砖块，用梯子爬最高的楼层
                ladders--;
                pq.add(need);
                bricks += pq.poll() - need;
            } else if (ladders == 0) {
                // 没梯子，砖头不够，到头了
                break;
            }

            index++;

        }
        return index;
    }
}
